home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Interactive Reference Guide / C-C++ Interactive Reference Guide.iso / c_ref / csource4 / 262_01 / symtbl.txt < prev    next >
Text File  |  1988-03-30  |  13KB  |  280 lines
  1. .he    /page #
  2. .ce 2
  3. A General Purpose Symbol Table Function Library
  4. by Robert Ramey
  5.  
  6. Many programs manipulate words with associated data.
  7. These programs have a lot in common but are often written
  8. from scratch when it is really not necessary.  This article
  9. presents a set of functions written in the "C" programming
  10. language which can be incorporated into any program without
  11. recompilation.  This will eliminate the time spent coding,
  12. debugging and compiling these functions for each new
  13. application.  Since one set of functions suffices for all
  14. symbol table applications,  program improvement is much
  15. easier.  Any improvements in the functions
  16. are automatically incorporated in the programs that use them.
  17. Finally,  the functions are reentrant in that even though
  18. a given program may use more than one type of symbol table
  19. there are only one set of functions.  This will make the
  20. final resulting program smaller.
  21.  
  22. An Illustration.  A Word Frequency Analysis Program.
  23.  
  24. Listing 1 shows how the functions are used in a simple program.
  25. The object of the program is to read one or more files of text
  26. and print out a table indicating the number of times each word
  27. is used.
  28.  
  29. The program starts by calling the function symmk() which allocates
  30. memory for management of the symbol table.  The first parameter
  31. is the size of the data structure to be associated with each
  32. symbol.  In this case that data structure is one integer to be
  33. used to accumulate the number of times that symbol is used.
  34. The second parameter is the hash frame factor.  For best
  35. results one should choose a number approximating the number of
  36. symbols expected to be placed in the table.  Why will become
  37. clear when the operation of the rountines is explained.
  38. The subrouine symmk() returns a pointer to a structure containing
  39. data used by the symbol table functions.  This pointer must be stored
  40. by the calling program and passed as a parameter when using
  41. any of the symbol table functions.  Its only useful
  42. function is to permit one program to use several types of
  43. symbol tables simultaneously.
  44.  
  45. Next the command line is processed.  Each file named is opened
  46. and the file is processed by the function ldwords().  This
  47. function retrieves each word through the function getwrd.
  48. The function symlkup() is used to check to see if the word is
  49. in the symbol table already.  If the word is already in the table
  50. symlkup() returns a pointer to
  51. the string found in the symbol table.  symdat() is called
  52. to retrieve the address of the data related to the symbol.
  53. Finally this data is incremented to indicate that the word
  54. in the symbol table has reoccurred in the text.
  55.  
  56. If the word is not found in the symbol table, symlkup() returns
  57. a NULL.  In this case symadd() is called.  symadd() like symlkup()
  58. returns a pointer to the new symbol in the text.  symdat() is
  59. again used to retrieve a pointer to data. This data is an
  60. integer to initialized with 1.
  61.  
  62. Once all words in the text have been reviewed,  we want to
  63. retrieve all the symbols with their data to print the frequency
  64. table.  The function symdmp() is called repeatedly to retrieve the
  65. pointer to each symbol.  The first parameter used by symdmp() is
  66. as usual the symbol table pointer.  The second parameter indicates
  67. that this is the initial call (0) or a subsecuent call (!=0).
  68. On each call, symdmp() returns a pointer to a symbol table entry
  69. or NULL indicating that there are no more symbols in the table.
  70. The symbol pointers are not returned in any useful sequence.
  71. However it is garenteed that each symbol will be returned once
  72. and only once.  Again symdat() is used to find the data given the
  73. symbol.  As each symbol is retreived it is displayed by calling the
  74. standard library function printf().
  75.  
  76. The Method Used.
  77.  
  78. The basic method used by the functions is well known to most
  79. programers and documented in all books on data management.  
  80. Given a symbol, a numeric value within a limited range is created
  81. using a simple algorithm.  This is called hashing the symbol.
  82. That numeric value is used as an index to select a chain of structures
  83. to which the symbol is added.  When it comes time to search for
  84. a symbol the numeric index is calculated and the corresponding
  85. chain of structures is sequencially searched.  This is much
  86. shorter than searching among all the symbols would be.
  87.  
  88. Data Structures Used.
  89.  
  90. When designing this family of functions I wanted them to be general
  91. and efficient for a wide range of applications.  This is the only
  92. way to discourage the temptation to fiddle with the code for each
  93. application.  This has led to slightly unusual use of the "C" language.
  94.  
  95. Two separate data structures are used.
  96. Neither structure can be described exactly in the "C" language.  The
  97. problem is that they are of variable length.  Hence, not all
  98. "C" constructs for dealing with structures can be used.
  99. When symmk() is called it returns a pointer to the following
  100. structure:
  101.  
  102. .nf
  103. .ne 14
  104. SYMBOLTABLE
  105.  
  106. Variable Name    Size        Function
  107. =============    ====        ========
  108. _element_size    sizeof(int)    contains the size of data structure
  109.                 associated with each symbol.
  110.  
  111. _hash_factor    sizeof(int)    contains the number of chains of
  112.                 symbols maintained.
  113.  
  114. _hash_table[1]    sizeof(SYMBOLENTRY *)    each element of the array
  115.         * (_hash_factor) points to the start of a chain of
  116.                 symbols.
  117. .fi
  118.  
  119. The _hash_table is declared to be an array of 1 element.
  120. One of the parameters used when symmk() is called is the hashing
  121. factor.  symmk() requests space sufficient store the above structure
  122. with this number of elements in _hash_table.  This ensures that
  123. although more than one element of _hash_table is accessed,  there
  124. will be no conflict with other storage in memory.  The "C" language
  125. does not prohibit access beyond array limits.  In fact _hash_table
  126. does not even have to be declared as an array.  I did so to make the
  127. more understandable.  We can use this structure in those operations
  128. which do not use its size.  That is, we can access elements through a
  129. structure pointer.
  130. However, we cannot use array syntax to access these structures,
  131. nor can we allocate fixed storage for such structures.
  132.  
  133. Each time symadd() is called a structure of the following type is
  134. created:
  135.  
  136. .nf
  137. .ne 13
  138. SYMBOLENTRY
  139.  
  140. Size        Function
  141. ====        ========
  142. (_element_size)    Contains data area to be filled and read by
  143.         calling functions.
  144.  
  145. sizeof(char *)    pointer to next symbol in chain.
  146.  
  147. sizeof(char *)    pointer to previous symbol in chain.
  148.  
  149. strlen(symbol)    NULL terminated string which is the symbol itself.
  150. .fi
  151.  
  152. This structure has no variable names because it is not explictly
  153. described in the code.  A symbol table entry consists of the
  154. data to be manipulated by the calling functions,  pointers for
  155. a two way linked list and a variable length string which is
  156. the symbol itself.  This structure permits flexiblity in data
  157. and symbol sizes.  However we cannot use the standard "C"
  158. language structure operators.  Pointers to symbol table entries
  159. contain the address of the character string which is the symbol
  160. itself.  Hence standard string manipulation functions such as
  161. strlen(), strcpy(), etc. can be used with no problem.
  162.  
  163. In order to retrieve the address of the data we must use a special
  164. function symdat() which returns a pointer to the data area of
  165. the symbol table entry.
  166. symdat() returns a character pointer.  However,  object pointed
  167. to is not a character.  It could be anything.  The value
  168. returned by symdat should always be cast to a pointer to the type
  169. of objects allocated.  This will permit the use symdat in
  170. constructs such as:
  171.  
  172.     (OBJECT *)symdat(symbol)->object_member = 0;
  173.  
  174. where OBJECT is a structure declared in the calling program.
  175. Failure to use casts in this case will result in execution
  176. errors on machines in which character pointers and other pointers
  177. have different formats.  Personally,  I think casts are underused.
  178. Often they will clarify what a piece of code is intended to do an
  179. help avoid particularly difficult hard to detect errors.  They take no
  180. runtime overhead unless they are really necessary, permit
  181. a program like LINT to be more useful, and make it much easier
  182. to port programs like this one to different machines.
  183.  
  184. Summary of Functions
  185.  
  186. In the table below the following types are assumed.  SYMBOLTABLE *
  187. is a pointer returned by a symmk() call. SYMBOLENTRY * is a character
  188. pointer containing the address of a symbol placed in the symbol table
  189. with the symadd() function.  Note that although this address can
  190. be used as string pointer to the value of the symbol,  the converse
  191. is not true.  That is a pointer to a string which is equal to the
  192. symbol not the same as a pointer to a symbol table entry.  Failure
  193. to make this distinction will produce disatrous results.
  194. In order to emphasize this distinction,  I have included the
  195. typedef statement defining SYMBOLENTRY as a character pointer.
  196.  
  197. .nf
  198. SYMBOLTABLE *
  199. symmk(data_size,hash_factor)    Initializes a symbol table.
  200.                 Returns pointer to symbol table
  201.                 structure if successful.
  202.                 Returns NULL if not enough memory
  203.                 available.
  204. SYMBOLENTRY *
  205. symlkup(SYMBOLTABLE *,symbol)    Given character string, returns symbol
  206.                 entry pointer if symbol is found in
  207.                 table.  Otherwise returns NULL.
  208. SYMBOLENTRY *
  209. symadd(SYMBOLTABLE *,symbol)    Adds symbol to symbol table
  210.                 allocating requiered data area.
  211.                 returns pointer to symbol if success-
  212.                 full, NULL otherwise.  Can only fail
  213.                 for lack of available memory.
  214. void
  215. symdel(SYMBOLTABLE *,SYMBOLENTRY *) Deletes symbol from symbol table.
  216.                 Returns no value.
  217. SYMBOLENTRY *
  218. symdmp(SYMBOLTABLE *,initial)    Retrieve each symbol once and only
  219.                 once.  Returns NULL if no more symbols
  220.                 in table.  Otherwise returns pointer
  221.                 to next symbol if initial == FALSE
  222.                 or first symbol if initial == TRUE.
  223. char *
  224. symdat(SYMBOLTABLE *,SYMBOLENTRY *) Returns character pointer
  225.                 containing address of data area.
  226. void
  227. symrmv(SYMBOLTABLE *)        Deletes the entire symbol table and
  228.                 returns allocated memory to memory
  229.                 manager.
  230. .fi
  231.  
  232. The operation of the functions is described within the code so I
  233. won't go into it here.  The manner of implementation has a number
  234. of implications if you use the functions.
  235.  
  236. There is no checking of parameters passed to functions.  This is done
  237. in order to make the functions as fast as possible.  Generally speaking
  238. I don't think that programs that pass correct parameters should be
  239. penalized because someone may write programs that pass incorrect ones.
  240. Besides no function could easily make the distinction anyhow.
  241.  
  242. symadd() does not check to see if the symbol already exists in the
  243. symbol table.  This means if your program is such that you can be
  244. sure symbols aren't repeated (sorted data for example) addsym wastes
  245. no time.  If you aren't careful you may add the same symbol
  246. to the table more than once.  In this case the functions symlkup(),
  247. and symadd() will return pointers to the last symbol entered.
  248. This can be very useful in some applications in which symbols have
  249. a temporary definition which differs from a more perminant one.
  250. An example of this is the "C" compiler which permits global and
  251. local symbols to be equal but with local symbols taking precedence.
  252. If the most recently added occurence of a symbol is deleted via
  253. symdel(), subsequent calls to symlkup() will return the previously
  254. added symbol.  This is extremely useful behavior is a side effect
  255. of the method of implementation of the functions symadd(), symlkup()
  256. and symdel().
  257.  
  258. Possible Improvements
  259.  
  260. The functions _nxtsym, _prvsym should really be implemented via
  261. preprocessor expansions.  I didn't do it as my preprocessor isn't
  262. complete.  symdat() should probably replaced in the calling
  263. program by a preprocessor expansion which includes proper
  264. type casting for each symbol table.  Routines could be added
  265. to save and reload entire symbol tables, thereby creating a system
  266. which can be used for indexing records.  The underlying algorithm
  267. could be altered or replaced to permit more operations such as
  268. sequencial retrieval of symbols, or retrieval of symbols given
  269. an approximate key.  None of these possible improvements would
  270. have to change the usage of the functions expained above.
  271. In fact, one could create a family of functions with different
  272. capabilities but all with the same usage.
  273.  
  274. Acknowledgements
  275.  
  276. The idea for this set of functions was pretty much stolen from
  277. our version of the RATFOR Software Tools package.  The functions have
  278. no author listed. The functions here are all new and exploit the
  279. flexiblity of "C".
  280.